package com.bestdreamer.arrays;

import java.util.Arrays;

public class QuickSortArrays {

    public static void quickSort(int[] array){
        int start = 0;
        int end = array.length -1;
        quickSort(array,start,end);
    }

    public static void quickSort(int[] arr,int low,int high){
        int start = low;
        int end = high;
        int key = arr[low];

        while(end > start){
            // 从后往前比较
            // 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
            while(end > start && arr[end] >= key){
                end --;
            }
            if(arr[end] < key){
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
            }
            // 从前往后比较
            // 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
            while(end > start && arr[start] <= key){
                start ++;
            }
            if(arr[start] >= key){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        // 此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，
            // 右边的值都比关键值大，但是两边的顺序还是有可能不一样，进行下面的递归调用
        }
        if(start > low){
            quickSort(arr,low,start-1);
        }
        if(end < high){
            quickSort(arr,end+1,high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {72,6,57,88,60,42,83,73,48,85};

        System.out.println(Arrays.toString(arr));

        quickSort(arr);

        System.out.println(Arrays.toString(arr));
    }
}
